package com.hardy.leetcode;

/**
 * 排序的链表
 * User: Ruijie Date: 2016/9/1
 */
public class ConvertSortedListToBinarySearchTree {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val=val;
        }
    }
    public static class ListNode{
        int val;
        ListNode next;
        public ListNode(int val){
            this.val=val;
        }
    }
    public static TreeNode sortedListToBST(ListNode head) {
        if (head==null){
            return null;
        }
        ListNode tail=head;
        while(tail.next!=null){
            tail=tail.next;
        }
        return CreateAVLTree(head,tail);
    }
    public static TreeNode CreateAVLTree(ListNode head,ListNode tail){
        TreeNode root;
        ListNode slow=head,fast=head,newEnd=head;
        if(head==tail){
            root=new TreeNode(head.val);
            return root;
        }
        while(fast!=tail&&fast.next!=tail){
            newEnd=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        root=new TreeNode(slow.val);
        if(newEnd!=slow){
            root.left=CreateAVLTree(head,newEnd);
        }
        root.right=CreateAVLTree(slow.next,tail);
        return root;
    }
    private static TreeNode process(ListNode head, ListNode tail) {
        if(head!=tail){
            ListNode mid=getMidListNode(head,tail);
            ListNode next=mid.next;
            mid.next=null;
            TreeNode node=new TreeNode(mid.val);
            ListNode preMid=getMidPreNode(head,mid);
            if(preMid!=null){
                node.left=process(head,preMid);
            }
            node.right=process(next,tail);
            return node;
        }
        if(head==tail){
            return new TreeNode(head.val);
        }
        return null;
    }

    private static ListNode getMidPreNode(ListNode head,  ListNode mid) {
        ListNode cur=head;
        if(head==mid){
            return null;
        }
        while(cur.next!=mid){
            cur=cur.next;
        }
        return cur;
    }

    private static ListNode getMidListNode(ListNode head,ListNode tail) {
        int len=0;
        ListNode cur=head;
        while(cur!=tail){
            len++;
            cur=cur.next;
        }
        int mid=len>>1;
        ListNode midNode=head;
        for(int i=0;i<mid;i++){
            midNode=midNode.next;
        }
        return midNode;
    }
    // for test -- print tree
    public static void printTree(TreeNode head) {
        System.out.println("Binary Tree:");
        printInOrder(head, 0, "H", 17);
        System.out.println();
    }

    public static void printInOrder(TreeNode head, int height, String to, int len) {
        if (head == null) {
            return;
        }
        printInOrder(head.right, height + 1, "v", len);
        String val = to + head.val + to;
        int lenM = val.length();
        int lenL = (len - lenM) / 2;
        int lenR = len - lenM - lenL;
        val = getSpace(lenL) + val + getSpace(lenR);
        System.out.println(getSpace(height * len) + val);
        printInOrder(head.left, height + 1, "^", len);
    }

    public static String getSpace(int num) {
        String space = " ";
        StringBuffer buf = new StringBuffer("");
        for (int i = 0; i < num; i++) {
            buf.append(space);
        }
        return buf.toString();
    }
    public static void main(String[] args) {
        ListNode node=new ListNode(1);
        node.next=new ListNode(2);
        node.next.next=new ListNode(3);
        node.next.next.next=new ListNode(4);
        node.next.next.next.next=new ListNode(5);
        TreeNode head=sortedListToBST(node);
        printTree1(head);
    }

    private static void printTree1(TreeNode head) {
        if(head!=null){
            printTree1(head.left);
            System.out.println(head.val);
            printTree1(head.right);
        }
    }
}
